


#include <stdio.h>

#include <stdlib.h>
#include <assert.h>
struct TreeNode 
{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};
typedef struct TreeNode BTNode;

int _preorder(struct TreeNode* root)
{
    if (root == NULL)
        return 0;

    return _preorder(root->left) + _preorder(root->right) + 1;
}
int _postorder(struct TreeNode* root, int* a, int* i)
{
    if (root == NULL)
        return 0;

    int l = _postorder(root->left, a, i);
    int r = _postorder(root->right, a, i);
    a[(*i)++] = abs(l - r);

    return l + r + root->val;
}
int findTilt1(struct TreeNode* root) {
    if (root == NULL)
        return 0;
    if (!(root->left || root->right))
        return 0;

    /*int cnt = _preorder(root);
    int a[cnt];*/
    int a[6];
    int i = 0;
    _postorder(root, a, &i);

    int sum = 0;
    for (i = 0; i < 6; ++i)
    {
        sum += a[i];
    }

    return sum;
}

int _dfs(struct TreeNode* root, int* ans)
{
    if (root == NULL)
        return 0;

    int l = _dfs(root->left, ans);
    int r = _dfs(root->right, ans);
    *ans += abs(l - r);

    return l + r + root->val;
}

int findTilt2(struct TreeNode* root)
{
    if (root == NULL)
        return 0;

    int ans = 0;
    _dfs(root, &ans);

    return ans;
}

BTNode* BuyNode(int x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    assert(node);

    node->val = x;
    node->left = NULL;
    node->right = NULL;

    return node;
}
//BTNode* CreateBTree(void)
//{
//    BTNode* n1 = BuyNode(1);
//    BTNode* n2 = BuyNode(2);
//    BTNode* n3 = BuyNode(3);
//    n1->left = n2, n1->right = n3;
//    
//    return n1;
//}
BTNode* CreateBTree(void)
{
    BTNode* n1 = BuyNode(4);
    BTNode* n2 = BuyNode(2);
    BTNode* n3 = BuyNode(9);
    BTNode* n4 = BuyNode(3);
    BTNode* n5 = BuyNode(5);
    BTNode* n6 = BuyNode(7);
    n1->left = n2, n1->right = n3;
    n2->left = n4, n2->right = n5;
    n3->right = n6;

    return n1;
}

int main()
{
    BTNode* root = CreateBTree();
    int cnt = _preorder(root);

    int ret = findTilt2(root);

    printf("%d\n", ret);

    return 0;
}
